Time division multiplexing (TDM) is one technique used to implement a switching system. A TDM switch consists of a central resource that operates at a bandwidth equal to the sum of the input and output port bandwidths. The central resource is partitioned via time slots that are allocated to the input and output ports. Typically, the central resource is a memory bus that writes packets that are received on the input ports and reads packets to be transmitted on the output ports. Although practical for small to medium sized switching systems, a TDM switch is limited in throughput by the bandwidth of the centralized memory bus. To scale beyond the bandwidth limitations of a single memory bus, multiple memories are used to implement individual queues. Although greater scaling is permitted with separate queues, performance usually suffers. Globally shared queues yield better performance since all of the switch queue resources can be dynamically allocated to data transients that would otherwise overload individual resources.
Consider a switch fabric with N input ports that each receive packets at rate R and N output ports that each transmit packets at rate R, as shown in FIG. 1. For a shared memory TDM switching system, a single memory bus is required that has an aggregate bandwidth of 2×N×R. The arriving packets are aggregated and written to the memory. Once written to memory, the packets are read out of the memory and transmitted on the output ports.
This system operates correctly and in a non-blocking fashion provided that the shared memory has enough bandwidth to service all of the input and output ports. Memory bandwidth can be increased by increasing the speed and width of the memory bus.
Data striping is effectively used in RAID (redundant array of inexpensive disks) video servers to reduce the BW and capacity requirements of disk drives when generating a high BW, high capacity video stream. In RAID-0 (RAID, level 0), a data stream is striped across several disk drives. In FIG. 2, a video stream is “striped” across three disk drives. The video server reads the striped information off of all three disks, reconstructs the video stream and outputs a single, high BW video stream. In the example system, the drive BW capacity is required to be one third of the video stream BW capacity.
In RAID-3 (RAID, level 3) a bit-wise parity data stripe is added to reconstruct data when a single disk fails. In the example in FIG. 3, the video stream is striped across three disks and a parity stripe is stored on a fourth disk. Consider a failure of drive 2 (the same argument is true for a failure of any one of the drives). The server reads the remaining data stripes with the parity stripe and reconstructs the missing data.
In the present invention, a centralized TDM switching system can be implemented with several memory banks, with all memory banks operating in concert. The total switch throughput is not limited by the bandwidth of a single memory bank, but by the total number of memory banks that can be interconnected in a switch. Even though multiple distinct memory banks are used, data is queued in a centralized and globally shared model. Data striping is used to implement a single global memory model across several banks. Data striping has been used effectively in RAID (redundant array of inexpensive disk) servers to reduce the bandwidth requirements on any single disk drive in the server. This invention applies the concepts of data striping to network switching systems.